package code;

import java.util.ArrayList;
import java.util.List;

public class Code37 {
	/*
	 * dfs填数独
	 */
	
	public boolean dfs(char[][] board,int step){
		int i,j;
		boolean isOk=true;
		for(i=0;i<9 && isOk;i++){
			for(j=0;j<9;j++)
				if(board[i][j]=='.'){
					isOk=false;
					break;
				}
		}
		if(isOk)
			return true;
		if(step==0)
			return false;
		System.out.println(step);
		
		boolean isFind=false;
		i=0;
		j=0;
		for(i=0;i<9 && !isFind;i++){
			for(j=0;j<9;j++){
				if(board[i][j]=='.'){
					/*
					 * 筛选可以填在这里的数字
					 * 行中没有出现的数字
					 * 列中没有出现的数字
					 * 小3*3矩阵没出现的字
					 */
					isFind=true;
					break;
				}
			}
			if(isFind)
				break;
		}
		if(!isFind)	return true;
		if(step==0)
			return false;
		System.out.println(step);
		
		int vis=0;
		int k;
		//第i行
		for(k=0;k<9;k++){
			if(board[i][k]=='.')
				continue;
			vis|=(1<<(board[i][k]-'0'));
		}
		//第j列
		for(k=0;k<9;k++){
			if(board[k][j]=='.')
				continue;
			vis|=(1<<(board[k][j]-'0'));
		}
		/*
		 * 以x=i/3*3,y=i/3*3为起点的3*3的格子
		 */
		int x=i/3*3,y=j/3*3;
		int l;
		for(k=x;k<x+3;k++)
			for(l=y;l<y+3;l++){
				if(board[k][l]=='.')
					continue;
				vis|=(1<<(board[k][l]-'0'));
			}
		/*
		 * vis[]=true的元素去掉，剩下的为可选元素
		 */
		List<Integer> list=new ArrayList<Integer>();
		/*
		 * 选择其中的一个数，填入格子
		 */
		for(k=0;k<list.size();k++){
			board[i][j]=(char)(list.get(k)+'0');
			if(dfs(board,step-1))
				return true;
			/*
			 * 若不满足则还原
			 */
			board[i][j]='.';
//		List<Integer> list=new ArrayList<Integer>();
		for(k=1;k<10;k++){
			if((vis&(1<<k))==0){
//				list.add(k);
				board[i][j]=(char)(k+'0');
				if(dfs(board,step-1))
					return true;
				/*
				 * 若不满足则还原
				 */
				board[i][j]='.';
			}
		}
		}
		return false;
	}
    public void solveSudoku(char[][] board) {
    	int step=0;
    	for(int i=0;i<9;i++){
    		for(int j=0;j<9;j++){
    			if(board[i][j]=='.')
    				step++;
    		}
    	}
        dfs(board,step);
    }
    public static void main(String[] args){
    	char[][] board={{'.','.','.','.','.','7','.','.','9'},
    			{'.','4','.','.','8','1','2','.','.'},
    			{'.','.','.','9','.','.','.','1','.'},
    			{'.','.','5','3','.','.','.','7','2'},
    			{'2','9','3','.','.','.','.','5','.'},
    			{'.','.','.','.','.','5','3','.','.'},
    			{'8','.','.','.','2','3','.','.','.'},
    			{'7','.','.','.','5','.','.','4','.'},
    			{'5','3','1','.','7','.','.','.','.'}};
    	new Code37().solveSudoku(board);
    	for(int i=0;i<9;i++){
    		for(int j=0;j<9;j++){
    			System.out.print(board[i][j]+" ");
    		}
    		System.out.println();
    	}
    }
}
